package com.sunny.example.string;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * DFS:采用递归 + 回溯
 */
public class HJ43_迷宫问题 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int lines = scanner.nextInt();//行数
            int rows = scanner.nextInt();//列数
            int[][] mg = new int[lines][rows];
            for (int i = 0; i < lines; i++) {//迷宫二维数组初始化
                for (int j = 0; j < rows; j++) {
                    mg[i][j] = scanner.nextInt();
                }
            }
            //1、先右，如果遇到1再下
            //2、如果右边到达边界，能下的话，再下。
            //3、以上如果不行，则回溯

            List<Node> list = new ArrayList<>();
            DFS(mg, 0, 0, list);
            for (Node node : list) {
                System.out.println("(" + node.x + "," + node.y + ")");
            }
        }
    }

    /**
     * 采用DFS来实现
     *
     * @param mg
     * @param x
     * @param y
     * @param list
     */
    private static boolean DFS(int[][] mg, int x, int y, List<Node> list) {
        Node oN = new Node(x, y);
        list.add(oN);
        //已经添加到路径中的，标记为1
        mg[x][y] = 1;

        //最右下角的结束位
        if (x == mg.length - 1 && y == mg[0].length - 1) {
            return true;
        }
        //向下走
        if (x + 1 < mg.length && mg[x + 1][y] == 0) {
            if (DFS(mg, x + 1, y, list)) {
                return true;
            }
        }
        //向下不能走时，向右走
        if (y + 1 < mg[0].length && mg[x][y + 1] == 0) {
            if (DFS(mg, x, y + 1, list)) {
                return true;
            }
        }

        //向右不能走时，向上走
        if (x - 1 >= 0 && mg[x - 1][y] == 0) {
            if (DFS(mg, x - 1, y, list)) {
                return true;
            }
        }

        //向上不能走，向左走
        if (y - 1 >= 0 && mg[x][y - 1] == 0) {
            if (DFS(mg, x, y - 1, list)) {
                return true;
            }
        }

        //如果都不行，则恢复状态，回溯
        list.remove(list.size() - 1);
        mg[x][y] = 0;
        return false;
    }

    public static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
